package com.zjsru.plan2023.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: cookLee
 * @Date: 2023-10-15
 * 只出现一次的数字 II
 */
public class SingleNumber {
    /**
     * 主要
     * \
     * 输入：nums = [2,2,3,2]
     * 输出：3
     * \
     * 输入：nums = [0,1,0,1,0,1,99]
     * 输出：99
     * \
     * @param args args
     */
    public static void main(String[] args) {
        SingleNumber singleNumber= new SingleNumber();
        int[] nums = new int[]{0,1,0,1,0,1,99};
        singleNumber.singleNumber(nums);
    }

    /**
     * 单号
     * 哈希map
     * @param nums nums
     * @return int
     */
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        return map.keySet().stream().filter(v -> map.get(v) == 1).findFirst().get();
    }


    /**
     * 单数2:位运算
     *
     * @param nums nums
     * @return int
     */
    public int singleNumber2(int[] nums) {
        //第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            /**
             * 这是因为其他元素都出现了三次，所以对于某一位，如果所有元素在这一位上出现的总次数不是3的倍数，那么出现一次的元素在这一位上的二进制值为1，否则为0。
             * */
            int total = 0;
            for (int num : nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}
